import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class CombinationSum {
    /*
    * 39. 组合总和
    * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
    * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。
    * 你可以按 任意顺序 返回这些组合。
    * candidates 中的 同一个 数字可以 无限制重复被选取 。
    * 如果至少一个数字的被选数量不同，则两种组合是不同的。
    * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
    *
    * 1 <= candidates.length <= 30
    * 2 <= candidates[i] <= 40
    * candidates 的所有元素 互不相同
    * 1 <= target <= 40
    * */
    public static void main(String[] args){

    }

    // 我的想法：因为可以重复，所以我们先排个序，从小到大，这样也方便我们剪枝
    // 还是因为可以重复，我们的start是可以从自己开始的，要递归之后再自增
    public List<List<Integer>> mySolution(int[] candidates, int target){
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backtracking(int[] candidates, int target, int start){
        if(target < 0)
            return;
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], start);    // 可以重复，所以传start， 而不是 +1
            start++;    // 为了防止结果重复，我们得在递归结束后让start自增，防止下次循环找回去
            path.pollLast();
        }
    }
}
